Графов теория - определение. Что такое Графов теория
Diclib.com
Словарь ChatGPT
Введите слово или словосочетание на любом языке 👆
Язык:

Перевод и анализ слов искусственным интеллектом ChatGPT

На этой странице Вы можете получить подробный анализ слова или словосочетания, произведенный с помощью лучшей на сегодняшний день технологии искусственного интеллекта:

  • как употребляется слово
  • частота употребления
  • используется оно чаще в устной или письменной речи
  • варианты перевода слова
  • примеры употребления (несколько фраз с переводом)
  • этимология

Что (кто) такое Графов теория - определение

РАЗДЕЛ ДИСКРЕТНОЙ МАТЕМАТИКИ, ИЗУЧАЮЩИЙ СВОЙСТВА ГРАФОВ
Графов теория
  • Денеш Кёниг]]
  • Псевдограф [[домино]] (28 костей)
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 40px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • Один из отцов современной теории графов Фрэнк Харари
  • Карта стран и соответствующий ей граф
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 45px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 45px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 45px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 45px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 45px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 45px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 30px
  • 40px
  • 40px
  • Мультиграф задачи о кёнигсбергских мостах
  • Леонард Эйлер]]
  • 500px
  • Доказательство без слов непланарности тессеракта. Вверху — тессеракт содержит <math>K_5</math>, внизу — <math>K_{3,3}</math>
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • 20px
  • Дерево Порфирия

ГРАФОВ ТЕОРИЯ         
раздел математики, особенность которого - геометрический подход к изучению объектов. Основное понятие теории - граф - задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа - схема метрополитена: множество станций (вершины графа) и соединяющих их линий (ребра графа).
Графов теория         

раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории - граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые (а может быть, и все) пары вершин. При этом пары вершин могут соединяться несколькими ребрами. Примеры графов: множество городов (вершины графа), например Московской области, и соединяющие их дороги (ребра графа); элементы электрической схемы и провода, соединяющие их. На рис. 1 изображен граф, вершинами которого являются станции городского метрополитена, а ребрами - пути, соединяющие соседние станции (одна из задач: указать какой-либо маршрут от станции А к станции В). Граф называется ориентированным, если на ребрах задана ориентация, т. е. указан порядок прохождения вершин. Наконец, в Г. т. изучаются графы, у которых ребрам приписаны какие-либо веса (или символы), а также графы, в которых выделены особые вершины, называются полюсами. Примеры: диаграмма состояний автомата, сеть ж.-д. путей с указанием на дугах их длин или пропускных способностей. На рис. 2 приведена схема автомобильных дорог между Москвой и Таллином; надо, например, выбрать маршрут минимальной общей длины пути из Москвы в Таллин (эти два города - полюсы сети); сравнение двух маршрутов Москва - Ленинград - Таллин и Москва - Витебск - Рига - Таллин показывает, что путь через Ленинград короче (1049 км).

Одной из первых работ по Г. т. можно считать работу Л. Эйлера (1736), относящуюся к решению головоломок и математических развлекательных задач. Первые глубокие результаты были получены в 1-й половине 20 в. в связи с решением задач построения электрических цепей и подсчёта химических веществ с различными типами молекулярных соединений. Однако широкое развитие Г. т. получила лишь с 50-х гг. в связи со становлением кибернетики и развитием вычислительной техники, когда Г. т. существенно обогатилась и новым материалом, и новыми подходами и когда началось систематическое изучение графов с разных точек зрения (структурной, информационной и т. д.). Именно в это время формулировались проблематика и методы Г. т. Г. т. находит применение в теории программирования и при построении вычислительных машин, в изучении физических, химических и технологических процессов, в решении задач планирования, в лингвистических и социологических исследованиях и т. д. Г. т. имеет тесные связи как с классическими, так и с новыми разделами математики; это - топология, алгебра, комбинаторный анализ, теория чисел, теория минимизации булевских функций. Г. т. включает большое число разнообразных задач. Одни из них группируются в отдельные направления, другие стоят более изолированно. Среди сложившихся разделов Г. т. следует отметить задачи, относящиеся к анализу графов, определению различных характеристик их строения, например выяснение связности графа: можно ли из любой вершины попасть в любую; подсчёт графов или их частей, обладающих заданными свойствами, например подсчёт количества деревьев с заданным числом рёбер (дерево - неориентированный граф без циклов); решение транспортных задач, связанных с перевозками грузов по сети. Решен ряд задач по синтезу графов с заданными свойствами, например построение графа с заданными степенями вершин (степень вершины - число выходящих из неё рёбер). Имеет прикладное и теоретическое значение задача о выяснении возможности расположения графа на плоскости без самопересечений его рёбер (т. е. является ли данный граф плоским), задача о разбиении графа на минимальное число плоских графов. Для некоторых задач Г. т. (выше были приведены далеко не все) были разработаны методы их решения. Среди них: метод Пойя перечисления и подсчёта графов с заданными свойствами, теорема и алгоритм Форда - Фалкерсона для решения транспортной задачи, "венгерский" алгоритм решения задачи о назначениях и т. д. Почти все задачи теории конечных графов (практически интересны именно графы с конечным числом вершин) могут быть решены путём перебора большого числа вариантов (т. н. полный перебор), поэтому для них требуется построение эффективных алгоритмов и использование быстродействующих вычислительных машин. Такими задачами являются: задача о раскраске вершин графа, задача об определении идентичности двух графов, Коммивояжёра задача. Есть задачи, требующие принципиального ответа, например задача о раскраске плоских графов, задача о восстановлении графа по его подграфам.

Лит.: Берж К., Теория графов и её применения, пер. с франц., М., 1962; Оре О., Графы и их применение, пер. с англ., М., 1965; Зыков А. А., Теория конечных графов. I, Новосибирск, 1969.

Рис. 1 к ст. Графов теория.

Рис. 2 к ст. Графов теория.

Теория графов         
Тео́рия гра́фов — раздел дискретной математики, изучающий графы. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг).

Википедия

Теория графов

Тео́рия гра́фов — раздел дискретной математики, изучающий графы. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг). Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, поскольку:

  • как и геометрия, обладает наглядностью;
  • как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
  • не имеет громоздкого математического аппарата («комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений»);
  • имеет выраженный прикладной характер.

На протяжении более сотни лет развитие теории графов определялось в основном проблемой четырёх красок. Решение этой задачи в 1976 году оказалось поворотным моментом истории теории графов, после которого произошло её развитие как основы современной прикладной математики. Универсальность графов незаменима при проектировании и анализе коммуникационных сетей.

Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее).

Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудности. В разных областях знаний понятие «граф» может встречаться под следующими названиями:

  • структура (гражданское строительство);
  • сеть (электротехника);
  • социограмма (социология и экономика);
  • молекулярная структура (химия);
  • навигационная карта (картография);
  • распределительная сеть (энергетика)

и так далее.

Что такое ГРАФОВ ТЕОРИЯ - определение